package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/restore-ip-addresses/'>复原 IP 地址(Restore IP Addresses)</a>
 * <p>有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如：
 * <ul>
 *     <li>"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址</li>
 *     <li>"0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。</li>
 * </ul>
 * </p>
 * <p>给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：s = "25525511135"
 *      输出：["255.255.11.135","255.255.111.35"]
 *
 *  示例 2：
 *      输入：s = "0000"
 *      输出：["0.0.0.0"]
 *
 *  示例 3：
 *      输入：s = "101023"
 *      输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length <= 20</li>
 *     <li>s 仅由数字组成</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/12 16:45
 */
public class LC0093RestoreIpAddresses_M {
    static class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> resList = new ArrayList<>();
            backtracking(s.toCharArray(), 0,  new ArrayList<>(4), resList);
            return resList;
        }

        private void backtracking(char[] chars, int startIdx, List<Integer> path, List<String> resList) {
            // 结束条件：正好四个整数
            if (path.size() == 4) {
                // 如果恰好使用完所有的字符，收集到一组答案
                if (startIdx == chars.length) {
                    StringBuilder joiner = new StringBuilder();
                    for (int i = 0; i < path.size(); i++) {
                        joiner.append(path.get(i));
                        if (i != path.size() - 1) {
                            joiner.append(".");
                        }
                    }
                    resList.add(joiner.toString());
                }
                return;
            }
            // 还没有出现4段整数，字符串就被使用完了
            if (startIdx == chars.length) {
                return;
            }
            // 以0 开头的字符，不符合规则。但0符合
            int currNum = 0;
            for (int i = startIdx; i < chars.length; i++) {
                currNum = currNum * 10 + (chars[i] - '0');
                // 1.值大于255，不符合规则
                // 2.当前数的第1位为0，但当前数不是0，说明出现了前导0的数，不符合规则
                if (currNum > 255 || (chars[startIdx] == '0' && i > startIdx)) {
                    break;
                }
                // 执行到这，说明：currNum<=255 并且当 chars[startIdx] == '0' 时， i == startIdx，不能有前导0，如果当前数值为0，那么当前ip地址一定为0
                path.add(currNum);
                backtracking(chars, i + 1, path, resList);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListString(solution.restoreIpAddresses("25525511135"));
        Printer.printListString(solution.restoreIpAddresses("0000"));
        Printer.printListString(solution.restoreIpAddresses("101023"));
    }
}
